package com.platform.modules.alg.alglib.poj2431;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Poj2431 {
    class MyComparator implements Comparator<Integer> {
        public int compare(Integer num1, Integer num2) {
            return num2.compareTo(num1);
        }
    }

    public String output = "";
    private final int N = 10005;
    int n, L, P;
    private node port[] = new node[N];

    public Poj2431() {
        for (int i = 0; i < port.length; i++) {
            port[i] = new node();
        }
    }

    void solve() {
        PriorityQueue<Integer> que = new PriorityQueue<>(new MyComparator());
        // ans:加油次数 pos:当前可到达的位置 k:第 k 个加油站
        int ans = 0, pos = P, k = 0;
        while (pos < L) {
            while (pos >= L - port[k].dis && k < n) {
                que.add(port[k].add);
                k++;
            }
            if (que.isEmpty()) {
                output = "-1";

                return;
            } else {
                pos += que.poll();
                ans++;
            }
        }
        output = "" + ans;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        for (int i = 1; i <= n; i++) {
            String[] nums = line[i].split(" ");
            port[i].dis = Integer.parseInt(nums[0]);
            port[i].add = Integer.parseInt(nums[1]);
        }
        String[] num = line[n + 1].split(" ");
        L = Integer.parseInt(num[0]);
        P = Integer.parseInt(num[1]);
        Arrays.sort(port);
        solve();
        return output;
    }
}


class node implements Comparable {
    public int dis; // 距离
    public int add; // 可加油量

    // 按距离降序
    @Override
    public int compareTo(java.lang.Object o) {
        return this.dis > ((node) o).dis ? -1 : 1;
    }
}
